package com.hao.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;

/**
 * TODO
 * 归并排序
 * @author 97472
 * @version 1.0
 * @date 2021/5/18 10:41
 */
public class MargetSort {
    public static void main(String[] args) {
        Random random = new Random();
        Integer[] arr = new Integer[10000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(10000000);
        }
        long start1 = System.currentTimeMillis();
        margetSort(arr);
        long end1 = System.currentTimeMillis();
        System.out.println("花费时间："+(end1-start1));
    }
    public static Integer[] sort(Integer[] arr){
        if (arr.length < 2){
            return arr;
        }else {
            int p = arr.length / 2;
            Integer[] arr1 = Arrays.copyOfRange(arr, 0, p);
            Integer[] arr2 = Arrays.copyOfRange(arr, p, arr.length);
            arr1 = sort(arr1);
            arr2 = sort(arr2);
            int i = 0;
            int j = 0;
            ArrayList<Integer> temp = new ArrayList<Integer>();
            while (i < arr1.length || j < arr2.length){
                if (i >= arr1.length){
                    temp.add(arr2[j]);
                    j++;
                    continue;
                }
                if (j >= arr2.length){
                    temp.add(arr1[i]);
                    i++;
                    continue;
                }
                if (arr1[i] >= arr2[j]){
                    temp.add(arr2[j]);
                    j++;
                }else {
                    temp.add(arr1[i]);
                    i++;
                }
            }

            return temp.toArray(arr);
        }
    }
    public static void margetSort(Integer[] arr){
        margetSort(arr,0, arr.length-1,new Integer[arr.length]);
    }
    private static void margetSort(Integer[] arr,Integer left,Integer right,Integer[] temp){
        if (right > left){
            int mid = (right - left) / 2 + left;
//            先将左右两边进行归并排序
            margetSort(arr,left,mid,temp);
            margetSort(arr,mid+1,right,temp);
            // 合并
            marget(arr,left,mid,right,temp);
        }
    }
    /**
     *  对数组进行合并排序
     * @param arr 数组
     * @param left 分数组的左边索引
     * @param mid 分数组的中间索引
     * @param right 分数组的结尾
     * @param temp 临时存放数据的数组
     */
    private static void marget(Integer[] arr,Integer left,Integer mid,Integer right,Integer[] temp){
        // 初始化，获取两个分数组的其实索引 其中[left mid]为一个分数组 [mid+1,right]为一个分数组
        // 已知该两个分数组已经实现排序
        int i = left;
        int j = mid+1;
        int k = 0;
        // 1进行比较合并
        while (i <= mid && j <=right){
            if (arr[i] <= arr[j]){
                temp[k] = arr[i];
                i++;
            }else {
                temp[k] = arr[j];
                j++;
            }
            k++;
        }
        // 2将剩余的分数组数据放入临时数组中
        while (i <= mid){
            temp[k] = arr[i];
            i++;
            k++;
        }
        while (j <= right){
            temp[k] = arr[j];
            j++;
            k++;
        }
        // 3将临时数组中的数据还原到原数组中去
        i = 0;
        while (i < k){
            arr[left] = temp[i];
            left++;
            i++;
        }
    }
    public static void printlnArr(Integer[] arr){
        for (int i = 0; i < arr.length; i++) {
            System.out.print(" " + arr[i]);
        }
        System.out.println();
    }
}
